from typing import List


class Solution:
    def minDifference(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        # 坐标压缩
        idx = set()
        for s, e in queries:
            idx.add(s - 1)
            idx.add(e)

        size = len(nums)

        # 计算每个位置的前缀和
        stat = [0] * 100
        cache = {-1: stat.copy()}
        for i in range(size):
            stat[nums[i] - 1] += 1
            if i in idx:
                cache[i] = stat.copy()

        # 计算结果
        ans = []
        for s, e in queries:
            # 计算当前子数组状态
            stat1 = cache[s - 1]
            stat2 = cache[e]
            now = [stat2[i] - stat1[i] for i in range(100)]

            res = 100
            last = -1
            for n in range(100):
                if now[n] > 0:
                    if last != -1:
                        res = min(res, n - last)
                    last = n
            if res != 100:
                ans.append(res)
            else:
                ans.append(-1)

        return ans


if __name__ == "__main__":
    print(Solution().minDifference(nums=[1, 3, 4, 8], queries=[[0, 1], [1, 2], [2, 3], [0, 3]]))  # [2,1,4,1]
    print(Solution().minDifference(nums=[4, 5, 2, 2, 7, 10], queries=[[2, 3], [0, 2], [0, 5], [3, 5]]))  # [-1,1,1,3]
